package Array;

import java.util.*;

/**
 * 380. O(1) 时间插入、删除和获取随机元素
 * 实现RandomizedSet 类：
 * RandomizedSet() 初始化 RandomizedSet 对象
 * bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
 * bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
 * int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
 * 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
 *
 * 解题思路：
 *  因为所有操作都要是O（1）时间复杂度完成的，所以我们需要一个容器来存储值与下标的关系，所以首先想到要使用哈希表
 *  然后我们需要考虑快速插入和删除，所以我们需要使用一个数组来存储实际的值，因为数组的插入与删除只需要O(1)的时间复杂度。
 *  -- 当我们插入一个值时， 需要判断这个值是否存在，而哈希表查询的时间复杂度是O（1） ， 所以先查哈希表，如果存在，则返回false，如果不存在，则哈希表添加当前元素和下标， 数组末尾添加当前值
 *  -- 当我们删除一个值时，需要判断这个值是否存在，查hash表，不存在返回false，如果存在，则拿到从hash表中获取的下标，将数组中的该下标中的值与数组末尾的值进行交换，然后删除数组末尾的值，最后删除哈希表中的记录
 *  -- 当我们获取一个随机数时，我们从数组的大小中随机获取一个下标，然后反查hash表，就完成了O（1）操作的获取随机值
 */
public class RandomizedSet {

    private List<Integer> nums;  // y有效数组
    private Map<Integer,Integer> valueIndexMap; // 值--下标哈希表
    private Random random;  // 随机数
    public RandomizedSet() {
        nums = new ArrayList<>();
        valueIndexMap = new HashMap<>();
        random = new Random();
    }

    public boolean insert(int val) {
        // 如果map的KeySet中存在此值，就返回false
        if(valueIndexMap.keySet().contains(val)){
            return false;
        }
        nums.add(val);
        // 添加值和下标,下标从0开始（nums.size()-1）
        valueIndexMap.put(val,nums.size()-1);
        // 数组添加值
        return true;
    }

    public boolean remove(int val) {
        // 如果map中的KeySet中不存在此值，就返回false
        if(!valueIndexMap.keySet().contains(val)){
            return false;
        }
        // 先获取该元素的位置
        Integer delIndex = valueIndexMap.get(val);
        // 将数组中末尾的元素设置到待删除的位置上
        Integer lastVal = nums.get(nums.size() - 1);
        nums.set(delIndex,lastVal);
        // 移除数组中的末尾元素，同时也需要更新Map中末尾元素的索引
        nums.remove(nums.size()-1);
        valueIndexMap.put(lastVal,delIndex);
        // 移除map中的记录
        valueIndexMap.remove(val);
        return true;
    }

    public int getRandom() {
        // 获取随机数,数组的查询为O（1）
        int index = random.nextInt(nums.size());
        return nums.get(index);
    }
}
